package edu.purdue.cs.ds;

import java.util.ArrayList;
import java.util.Random;

/**
 * Splits a secret according to a randomly generated polynomial
 * of degree k, generating n shares.
 * @author jwallrab
 *
 */
public class ShamirSecret {
	
	String secret;
	final Integer maxCoefficient = 1024;
	ArrayList<ShamirShare> sharing;
	int k = -1;
	int n = -1;
	
	/**
	 * Constructor for Reconstructing the Secret
	 * @param shares
	 */
	public ShamirSecret(ArrayList<ShamirShare> shares, int kval, int nval){
		
		n = nval;
		k = kval;
		sharing = shares;
	}

	/**
	 * Create a sharing of the secret string
	 * @param s
	 */
	public ShamirSecret(String s, int kval, int nval){
		
		n = nval;
		k = kval;
		secret = s;
		sharing = split();
	}
	
	/**
	 * Split the secret n ways such that any k shares can
	 * recover the original secret 
	 * @param k
	 * @param n
	 * @return
	 */
	public ArrayList<ShamirShare> split(){
		
		ArrayList<ShamirShare> sharing = new ArrayList<ShamirShare>();
		double constant = Double.parseDouble(secret);
		
		System.out.println("*** Splitting Secret ***");
		
		Random r = new Random();
		ArrayList<Integer> coefficients = new ArrayList<Integer>();
		
		System.out.print("Polynomial: " + constant);
		
		for(int i = 0; i < k; ++i){
			coefficients.add(r.nextInt(maxCoefficient));
			System.out.print(" + " + coefficients.get(i) + "x^" + (i+1));
		}
		System.out.println();
		
		for(int i = 1; i <= n; ++i){
			sharing.add(getShare(i,coefficients,constant));
			System.out.println("Share: " + sharing.get(i-1).toString());
		}
		
		System.out.println("");
		
		return sharing;
	}
	
	/**
	 * Get a sharing as (x, p(x)) given the secret and coefficients
	 * @param x
	 * @param coef
	 * @param sec
	 * @return
	 */
	public ShamirShare getShare(int x, ArrayList<Integer> coef, double sec){
		
		double fx = sec;
		
		for(int i = 0; i < coef.size(); ++i)
			fx += coef.get(i) * Math.pow(x,i+1);
		
		return new ShamirShare(x, fx);
	}
	
	/**
	 * Returns the shares of the secret
	 * @return
	 */
	public ArrayList<ShamirShare> getShares(){
		return sharing;
	}
	
	/**
	 * Returns the reconstructed secret L(0)
	 * @return
	 */
	public String reconstruct(){
		
		Double lx = 0.0;
		for(int i = 0; i <= k; ++i)
			lx += sharing.get(i).getFx() * lagrangeBasisPolynomial(i);
		
		System.out.println("Reconstructed Secret: " + lx);
		
		return Double.toString(lx);
	}
	
	
	/**
	 * Calculates the Lagrange Basis Polynomial l_j(x)
	 *\Pi_{0\leq i \leq k, i \neq j} \frac{x-x_m}{x_j - x_m}
	 */
	public double lagrangeBasisPolynomial(int j){
		
		double ljx = 1.0;
		
		for(int i = 0; i <= k; ++i)
			if(i != j)
				ljx *= (0-sharing.get(i).getX())/(double)(sharing.get(j).getX()-sharing.get(i).getX());
		
		return ljx;
	}
	
}
